Esercitazione 3

Soluzioni esercizi per casa

Esercizio 2.2: soluzione

Il programma usa repne scasb per scorrere il vettore finché non trova il carattere in %al, cioè _. Dopo la prima scansione, salva l'indirizzo attuale per usarlo come indirizzo di partenza della sottostringa. Dopo la seconda scansione, fa una sottrazione di indirizzi per trovare il numero di caratteri che compongono la sottostringa. Usando indirizzo di partenza e numero caratteri, stampa quindi a terminale.

I bug da trovare sono i seguenti:

• Le istruzioni rep utilizzano %ecx, ma la riga 17 inizializza solo %cx. Questo funziona solo se, per puro caso, la parte alta di %ecx è a 0 ad inizio programma.
• L'istruzione scasb ha l'indirizzo del vettore come destinatario implicito in %edi, non %esi.
• La repne scasb termina dopo aver scansionato il carattere che rispetta l'equivalenza. Questo vuol dire che dopo la prima scansione abbiamo l'indirizzo del carattere dopo il primo _ (corretto) ma dopo la seconda scansione abbiamo l'indirizzo del carattere dopo il secondo _: la sottrazione calcola una sottostringa che include il _ di terminazione.
• Il sottoprogramma usato è quello sbagliato: outline stampa finché non incrontra \r, per indicare il numero di caratteri da stampare va usato outmess.

Il codice dopo le correzioni è quindi il seguente, scaricabile qui.

.include "./files/utility.s"

.data

msg_in: .fill 80, 1, 0

.text
_main:  
    nop
    mov $80, %cx
    lea msg_in, %ebx
    call inline

    cld
    mov $'_', %al
    lea msg_in, %edi
    mov $80, %cx

    repne scasb
    mov %edi, %ebx
    repne scasb
    mov %edi, %ecx
    sub %ebx, %ecx
    dec %ecx
    call outmess

    ret

Si sottolinea inoltre una debolezza della soluzione: la sottrazione fra puntatori funziona solo perché la scala è 1, cioè maneggiamo valori da 1 byte, per cui c'è corrispondenza fra la differenza di due indirizzi e il numero di elementi fra loro. Una soluzione più robusta è utilizzare la differenza del contantore %ecx anziché di puntatori. In alternativa, si può utilizzare shift a destra dopo la sottrazione per tener conto di una scala maggiore di 1, ma è un metodo che rende facile sbagliare (bisogna stare attenti all'ordine tra shift e decremento). Si può verificare come un simile esercizio basato su word, per esempio con serie di valori decimali delimitati da 0.

Esercizio 2.3: soluzione

Il programma dell'esercizio 2.2 viene complicato dalla richiesta di gestire dei valori di default, in caso siano presenti uno o nessun delimitatore _. Questo vuol dire gestire il caso in cui una repne scasb termina non perché ha trovato il carattere, ma perché %ecx è stato decrementato fino a 0.

Questo si implementa come dei semplici check su %ecx dopo ciascuna repne scasb, in caso sia 0 si va ad un branch separato: se succede alla prima scansione non è presente alcun _ e saltiamo quindi a print_all, se succede alla seconda scansione abbiamo solo un _ e saltiamo quindi a print_from_start. Altrimenti, si prosegue con lo stesso codice dell'esercizio 2.2, che nomineremo print_substr.

Per print_all basta una semplice outline dell'intera stringa. Per print_from_start, si fa un ragionamento non dissimile da quanto visto per l'esercizio precedente, dove va usato come inizio l'indirizzo di msg_in e il numero di caratteri può essere calcolato, come prima, usando l'indirizzo che troviamo in %edi dopo la prima repne scasb.

Il codice risultante è il seguente, scaricabile qui.

.include "./files/utility.s"

.data

msg_in: .fill 80, 1, 0

.text
_main:  
    nop
    mov $80, %cx
    lea msg_in, %ebx
    call inline

    cld
    mov $'_', %al
    lea msg_in, %edi
    mov $80, %ecx

    repne scasb
    cmp $0, %ecx
    je print_all

    mov %edi, %ebx
    repne scasb
    cmp $0, %ecx
    je print_from_start

print_substr:
    mov %edi, %ecx
    sub %ebx, %ecx
    dec %ecx
    call outmess
    ret

print_from_start:
    mov %ebx, %ecx
    lea msg_in, %ebx
    sub %ebx, %ecx
    dec %ecx
    call outmess
    ret

print_all:
    lea msg_in, %ebx
    call outline
    ret

Esercizio 3.1: esercizio d'esame 2021-01-08

Il testo con soluzione si trova qui.

Provare da sé

Provare a svolgere da sé l'esercizio, prima di guardare la soluzione o andare oltre per la discussione.

Questo esercizio pone principalmente tre spunti.

Il primo è la gestione dell'input, da eseguire con un loop di inchar e controlli, facendo outchar solo quando il carattere è accettato. Questo è stato già visto, per esempio, nell'esercizio 1.8.

Il secondo spunto riguarda il dimensionamento dei dati da gestire. Infatti, dobbiamo scegliere se usare 8, 16 o 32 bit, e possiamo farlo solo cercando di capire su quanti bit sta il numero più grande che possiamo gestire.

Data la natura del problema, è facile intuire che questo si trova quando $N = 9$ e $k = 9$. Dovremmo stampare un triangolo 9 righe, ciascuna composta da 1 a 9 numeri, a partire da 1 e di passo 9. Da una parte, potremmo ricordarci questa è una sequenza nota: la somma di $1 + 2 + ... + n$ è $\frac{n(n+1)}{2}$, quindi abbiamo $9 \cdot 10/2 = 45$ elementi. Tuttavia, un approccio più semplice porta a un risultato simile: di sicuro il triangolo avrà meno elementi di un quadrato di lato 9, composto da $9 \cdot 9 = 81$ elementi e, dato che la diagonale è inclusa, avrà più della metà di questo, cioè $81 / 2$. Possiamo quindi dire con questo ragionamento che sono più di $41$ elementi e meno di $81$, mentre usando la formula esatta troviamo che sono $45$.

Dato che incrementiamo di passo 9 ogni volta, il numero di posizione $j$ sarà $(j-1) \cdot 9 + 1$. Considerando per la stima di prima il 41-esimo elemento, abbiamo $40 \cdot 9 + 1 = 361$, mentre l'81-esimo elemento (che non sarà mai presente) sarebbe $80 \cdot 9 + 1 = 721$. Il valore esatto, se ci ricordiamo la formula di cui sopra, è invece $44 \cdot 9 + 1 = 397$. Un tale numero deve essere rappresentato su più di 8 bit, ma sta senza problemi in 16 bit: svolgeremo quindi i nostri calcoli usando delle word di 16 bit.

Non resta quindi che fare la stampa del triangolo. Questo si può scrivere come un doppio loop, dove il loop interno usa il contatore esterno per determinare quando uscire stampando una nuova riga, mentre un registro contatore viene utilizzato durante ogni ciclo per calcolare il nuovo numero da stampare. In (pseudo) C, tale ciclo avrebbe una forma simile:

short c = 1; // word da 16 bit
for(int i = 0; i < n; i++) {
    for(int j = 0; j < i + 1; j++) {
        outdecimal_word(c);
        outchar(' ');
        c += k;
    }
    outline()
}

Esercizio 3.2: esercizio d'esame 2021-09-15

Il testo con soluzione si trova qui.

Provare da sé

Provare a svolgere da sé l'esercizio, prima di guardare la soluzione o andare oltre per la discussione.

Questo esercizio ci chiede di leggere una stringa e poi analizzarne i caratteri, contando le occorrenze di alcuni di questi.

La lettura si può svolgere con la inline. Dopodiché, viene la parte di scansione e stampa. Si possono individuare due strategie, entrambe accettate in sede d'esame.

Nella prima strategia, si mantiene un vettore di conteggio (16 celle da 1 byte inizializzate a 0) e si scansiona la stringa una volta sola. Ogni qualvolta si trova un carattere d'interesse, se ne calcola l'indice e si incrementa la cella corrispondente del vettore. Per il calcolo di tale indice, basta fare sottrazioni e somme ragionando sul valore numerico della codifica ASCII, come visto nell'esercizio 2.1. Per esempio, dato un carattere $c$ di valore compreso tra $'a' e $'f', il valore corrispondente (e dunque l'indice del vettore) sarà $c - 'a' + 10$. Alla fine di questa scansione della stringa, si scansione il vettore di contatori stampando una riga per contantore, facendo il processo inverso per la conversione da indice a cifra esadecimale.

Nella seconda strategia, si sfrutta il fatto che le stampe sono in ordine, e ciascuna su una riga separata. Possiamo quindi evitare il vettore di contatori, e scansionare la stringa una volta per cifra esadecimale contando le occorrenze di quella specifica cifra e stampandone la riga corrispondente immediatamente, anziché ad un passaggio successivo dopo aver salvato il conteggio in memoria.

In termini di complessità algoritmica, la prima strategia è $O(n_{cifre})$ in memoria e $O(n_{stringa}) + O(n_{cifre})$ in tempo, la seconda strategia è $O(1)$ in memoria e $O(n_{cifre} \cdot n_{stringa})$ in tempo. Questo è un esempio classico di trade-off tra cicli di calcolo e occupazione della memoria, che porta a differenti scelte ottime in base alle condizioni del problema. Mentre nelle condizioni semplici in cui operiamo la differenza è decisamente esigua, con i due $n$ che sono soltanto 80 e 16, in casi più complessi vincerà una strategia sull'altra a seconda delle natura del problema.

In poche parole, per l'esame: vanno entrambe bene.

Va specificato però cosa non andrebbe bene: scrivere 16 o più blocchi di codice simile, dove cambia solo il carattere, inserito come letterale, usato per il confronto. Quale che sia la strategia utilizzata, il codice va generalizzato in modo da usare le stesse istruzioni per operazioni simili e minimizzare i punti da cui può scaturire un errore.